Maneuvering in three-dimensional space requires some type of navigation scheme, be it passive or active, that requires a safe path from a start point to a goal. Path planning between these points is a relatively straight forward problem in free space without obstacles. However, path planning becomes more difficult when obstacles are encountered in the three-dimensional space. In this situation, the collision free space must be defined and a path calculated which can be utilized in the navigation system.
The general path planning schemes utilized to define the collision free path are known as the "Find-Path" problems which find applications in the robotics and similar industries. There are two basic approaches for the "Find-Path" problem. The first approach represents the obstacles explicitly as geometrical shapes, like polygons, with the free space being defined implicitly as that space outside those obstacles. In one example of this approach, a spatial graph is generated which represents all of the visible paths between the vertices of obstacles and start and goal locations known as the Visibiity graph, T. Lozano-Perez and M. A. Wesley, "An Algorithm for Planning Collision-Free Paths Among Polyhedra Obstacles", Communications Association of Computing Machinery, Vol. 22, 1979. The other basic approach represents the free space explicitly and finds the path directly inside the free space. In one example of this approach, free space is represented as generalized cones with a central axis of these cones forming a connected path or passing channels, R. Brooks, "Solving the Find-Path Problem by Good Representation of Free Space", IEEE Transaction on System, Man and Cybernetics, Volume SMC-13, No. 3, 1983.
The path finding process for either these approaches searches for the path on the connectivity graph. By definition, the path found is therefore a safe path, i.e. collision free. One of the disadvantages of both approaches has been the high computational cost in finding the shortest path in three-dimensional space.
In solving the "Find-Path" problem, a spatial graph of some type is generated to provide a set of all safe points in the maneuverable free space which represents a given terrain map. It is then necessary to find the shortest path along the maneuverable space. There are two problems that can be encountered when maneuvering in the free space which represents a given terrain map. First, there is a location uncertainty as to the actual navigational path as compared to the calculated path which, if not considered, could result in collision with a boundary of the obstacles, which is also an inherent boundary of the free space. Second, there is a possibility that an unexpected obstacle not accounted for on the given terrian map could occur in the three-dimensional space, thus blocking a portion of the free space. With respect to the uncertainty measure of the location, this is a variable that can change at any time during navigation of a particular path depending upon the type of vehicle that is being navigated, the type of terrain over which it is being navigated and the type of navigation system that is being utilized. Therefore, it is difficult to predict what the uncertainty profile will be over the entire path when an initial path is generated therefore. With respect to an unexpected obstacle, this is typically something that would be detected during the navigation of a particular path which, of course, would render the spatial graph from which the path was determined invalid. These two factors are more important when navigating over a large area where localized sensors and the such are of little use.
In order to realize a practical solution to the "Find-Path" problem over a large section of a three-dimensional space, it is necessary to have a system that requires a relatively small computational budget that is capable of responding to instantaneous changes in both the maneuverable space and also in the navigational system. The present systems, as such, do not account for any variables like location uncertainty and unexpected obstacles in the navigation scheme or in the navigational space. There therefore exists a need for a navigational system that is capable of accounting for such changes that occur during navigation of a particular region.